package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
        Solution solution = new Solution();
        Solution2 solution2 = new Solution2();

        // 测试二分查找
        System.out.println("=== 二分查找测试 ===");
        int[] nums1 = {-1, 0, 3, 5, 9, 12};
        System.out.println("数组: " + Arrays.toString(nums1));
        System.out.println("查找 9: " + solution.search(nums1, 9));    // 输出: 4
        System.out.println("查找 2: " + solution.search(nums1, 2));    // 输出: -1
        System.out.println("查找 -1: " + solution.search(nums1, -1));  // 输出: 0
        System.out.println("查找 12: " + solution.search(nums1, 12));  // 输出: 5

        // 测试查找第一个和最后一个位置
        System.out.println("\n=== 查找第一个和最后一个位置测试 ===");
        int[] nums2 = {5, 7, 7, 8, 8, 10};
        System.out.println("数组: " + Arrays.toString(nums2));
        System.out.println("查找 8: " + Arrays.toString(solution2.searchRange(nums2, 8)));    // 输出: [3, 4]
        System.out.println("查找 7: " + Arrays.toString(solution2.searchRange(nums2, 7)));    // 输出: [1, 2]
        System.out.println("查找 6: " + Arrays.toString(solution2.searchRange(nums2, 6)));    // 输出: [-1, -1]

        int[] nums3 = {5, 7, 7, 8, 8, 8, 8, 10};
        System.out.println("\n数组: " + Arrays.toString(nums3));
        System.out.println("查找 8: " + Arrays.toString(solution2.searchRange(nums3, 8)));    // 输出: [3, 6]
        System.out.println("查找 5: " + Arrays.toString(solution2.searchRange(nums3, 5)));    // 输出: [0, 0]
        System.out.println("查找 10: " + Arrays.toString(solution2.searchRange(nums3, 10)));  // 输出: [7, 7]

        int[] nums4 = {};
        System.out.println("\n空数组测试: " + Arrays.toString(solution2.searchRange(nums4, 0))); // 输出: [-1, -1]
    }

    // 二分查找
    static class Solution {
        public int search(int[] nums, int target) {
            // 1) 初始化左右边界
            int left = 0, right = nums.length - 1;

            // 2) 二分搜索
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (target < nums[mid]) {
                    right = mid - 1; // 目标在左半部分
                } else if (target > nums[mid]) {
                    left = mid + 1; // 目标在右半部分
                } else {
                    return mid; // 找到目标
                }
            }
            // 3) 未找到返回 -1
            return -1;
        }
    }

    // 在排查数组中查找元素的第一个和最后一个位置
    static class Solution2 {
        public int[] searchRange(int[] nums, int target) {
            // 1) 边界处理
            int[] result = new int[2];
            result[0] = result[1] = -1;
            if (nums.length == 0) return result;

            // 2) 二分查找左边界
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid; // 保留可能的左边界
                }
            }
            // 3) 验证左边界是否为目标值
            if (nums[left] != target) return result;
            result[0] = left;

            // 4) 二分查找右边界
            left = 0;
            right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left + 1) / 2; // 向上取整避免死循环
                if (nums[mid] <= target) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            result[1] = left;
            // 5) 返回结果
            return result;
        }
    }
}